The present invention relates to digital data encryption. More particularly, the invention relates to data encryption using very long binary sequences (keystream) generated from a sequence generator using initialization parameters, such as a quasi-crystal generator, as described herein.
Some current encryption practices known as stream ciphers are based on the use of a keystream generated from an encryption key and which encrypts plaintext into ciphertext according to an encryption scheme. The most common and simple-to-compute encryption scheme is the exclusive-OR or XOR logic function. In the encryption processor, the ciphertext is generated by XOR""ing the computer-word-size blocks of the plaintext with the corresponding computer-word-size blocks of the keystream. To decrypt the message, the same keystream generated using the same key is XOR""ed with the ciphertext to obtain the original plaintext. If the key space is as large as the plaintext space, in which case the key is used as the keystream, and if there is no repetition of the use of the key, the encryption is considered to be unconditionally secure. This encryption process is called a one-time pad.
In such encryption, both the sender and the receiver must share the key. The transmission of the key must be carried out using a secure channel, or using a secure encryption scheme over an unsecure channel. If the key is very long, the transmission of the key creates greater overhead for the encryption communication. This motivates the design of stream ciphers where the keystream is pseudo-randomly generated from a smaller secret key. Common stream ciphers are based on cryptographically secure pseudo-random bit generators (CSPRBG""s).
The use of pseudo-random number generators (PRNG""s) to provide a stream cipher is known in the art. According to this technique, the shared secret (short) key represents parameters used in PRNG and a stream is obtained from a sequence of pseudo-random generated numbers. This stream is then used for enciphering the plaintext at the sender""s end and deciphering the ciphertext at the receiver""s end.
PRNGs are much more computationally efficient than CSPRBG""s, however they are not cryptographically secure. PRNG""s are periodic, and while their period may be very long, specific patterns of the sequence indicate position in that sequence, and it becomes possible for an attacker having some knowledge of the plaintext to determine the position in the periodic sequence and break the cipher. In some cases, PRNG""s are so unsecure that an attacker may obtain directly the type of PRNG used only from looking at a small part of the sequence.
U.S. Pat. No. 5,835,597 to Coppersmith et al. and assigned to IBM describes a software-efficient pseudo-random function which maps an index and an encryption key to a pseudo-random bit string useful for constructing a stream cipher. The method begins by preprocessing the encryption key into a table of pseudo-random values. The index and a set of values from the table is then used to generate a set of initial values for the registers. At least some of the register values are modified in part by taking a current value of a register and replacing the current value with a function of the current value and a value retrieved from the table, the latter value being determined by the values in one or more other registers. After modifying the register values in this fashion, the values are masked using other values from the table and the results then concatenated into the pseudo-random bit string. The modification step is repeated and a new masked function of the register values is then concatenated into the pseudo-random bit string. The modification and concatenation steps are repeated to continue growing the pseudo-random bit string until the string reaches some desired length. The publicly known pseudo-random functions lack true randomness and/or require significant computational effort.
It is an object of the present invention to provide a method and apparatus for generating very long binary keystreams. This is done in two main steps: first by generating sequences which are aperiodic and simple to compute, and then by coloring selected elements of the sequences, that is attributing binary strings to selected elements of the sequences.
The invention also provides for the use of PRNG""s in combination with aperiodic functions, functions which generates a series of values in an unpredictable manner without any periodic repetition of the series. Aperiodic functions, which can be obtained from quasi-crystals, can be used in order to hide all non-randomness in the PRNG""s.
The invention provides a method of encrypting data comprising:
a) defining symmetric key parameters specifying at least one quasi-crystal function and a starting point;
b) calculating consecutive aperiodic values of the quasi-crystal function;
c) using the aperiodic values of the quasi-crystal function in a predetermined process of generating a series of encryption pad values, the predetermined process being defined by the key parameters; and
d) encrypting the data using the pad values.
The method can be used for encrypting a message to be transmitted, and of course for decrypting an encrypted message received. The invention may be used to provide terminal equipment with modest processing power for carrying out the encryption and description for digital communications.
The invention also provides a method of applying a digital watermark to a selected portion of a document, the selected portion being modifiable without being easily detected, the method comprising:
applying a quasi-crystal transformation to the selected portion of the document;
applying a watermark to the transformed selected portion; and
applying an inverse quasi-crystal transformation to the watermarked selected portion. Preferably, the quasi-crystal transformation is a two-dimensional transformation. The watermark applied to the transformed selected portion may comprise a visually identifiable mark.
The encryption method according to the invention has no analog in current cryptographic practice. Its encryption class may be considered to be situated between the one-time-pad method and the stream cipher method with a secret symmetric encryption key. It can be used either for transmission of digital data or as an identification system, allowing a number of hybrid variants and combinations with other encryption types such as block ciphers and watermarks. The encryption system makes use of truly infinite, completely aperiodic point sets (referred to herein as quasi-crystals) which can be generated by a fast algorithm in any dimension from a few real numbers provided in the encryption key. In the one-dimensional case, the points can be taken simply as a discrete set of real numbers, in n-dimensions these are points of an n-dimensional Euclidean space, that is n-tuples of real numbers. The distances between adjacent points along any direction (in n-dimensional quasi-crystal) can take only a small number of distinct values. More information on 2-dimensional quasi-crystals, is given hereinbelow in the description of the watermark embodiment.
The advantage of exploitation of quasi-crystals in comparison with prior art cryptographic methods include:
It can be used for encryption of any type of digital data and of any dimension (for parallel data transmission).
The keystream is derived from quasi-crystal points transformed into a binary form. It can be infinite and aperiodic in the strongest sense: it contains no periodic subsets. Therefore linguistic analysis of the encrypted message is useless: repeated words are encrypted differently: partial knowledge of the content of the encrypted message can be of no help for decryption of the rest of the mesage.
The encryption can be very fast. Quasi-crystals can be generated point by point in real time during the data encryption and decryption, starting from any of its points (seed point). A single quasi-crystal point can be used to encrypt several bits at once.
An encryption (or equivalently enciphering) key is used. It consists of only a few real numbers which determine uniquely all of the infinity of quasi-crystal points and may contain other encryption information as well, such as starting colors. These parameters can be selected by the algorithm specifically for each encryption or can be changed during the encryption according to a prescribed protocol.
There is an infinite number of different quasi-crystals even in one-dimension.
Properties of the keystream may exclude the existence of a mathematical breaking of the encryption without the key.
The method is readily amenable to parallel processing both during encryption and decryption because the same quasi-crystal can be generated from several (many) seed points simultaneously.
The encryption can be made either as a stream cipher or as a block cipher or use to generate digital watermarks.
The novelty of the method consists in systematic use of aperiodic infinite point sets called by several names in the mathematics and physics literature: cut and project sets, model sets, Meyer sets, quasi-crystals, or even quasi-lattices. A lot of properties of such sets are found in the literature (reference may be had to the following: C. Janot, Quasi-crystals: A Primer, Oxford University Press, Oxford, 1994; The Mathematics of Aperiodic Long Range Order, Proc. NATO Advanced Study Institute, Waterloo, Ont. 1995, published by Kluwer Scientific Publishers, ed. R. V. Moody, 1997; and Quasi-crystals and Discrete Mathematics, The Fields Institute Monograph Series, Vol. 10, 1998, American Math. Society, Providence R.I., ed. Jiri Patera). Such quasi-crystal sets have not yet been used before in cryptography. Geometrically, one-dimensional quasi-crystals are constructed as shown in FIG. 1. A two-dimension lattice, for example Z2, is drawn in the plane along with two perpendicular straight lines p and pp with irrational slopes, for example xcfx84 and xcfx84xe2x80x2. Any interval xcexa9=(c,d) on the line pp determines a strip in the plane parallel to the line p. The quasi-crystal is formed by the projections of the Lattice points within the strip on to the line p. The interval xcexa9 is called the acceptance window of the quasi-crystal xcexa3(xcexa9). In FIG. 1, the elements of the lattice generating quasi-crystal points are marked by full dots and the projection on the line p is illustrated by segments joining these points and the line p.
The new encryption method according to the present invention makes use of specific properties of quasi-crystals demonstrated in Applicants"" recent series of articles: Z. Masakovxc3xa1, Jiri Patera, E. Pelantovxc3xa1, Inflation centers in cut and project quasi-crystals, Jiri Phys. A: Math. Gen., 31 (1998) 1443-1453: Z. Masakovxc3xa1, Jiri Patera, E. Pelantovxc3xa1, Minimal distances in quasi-crystals, J. Phys., A: Math. Gen., 31 (1998) 1539-1552; Z. Masakovxc3xa1, Jiri Patera, . Pelantovxc3xa1, Selfsimilar Delone sets and cut and project quasi-crystals, J. Phys., A: Math. Gen., 31 (1998) 4927-4946. A further paper of interest is the paper given by P. Pleasants, in the Proc. of the 5th Conference on Quasicrystals, Avignon, 1995.
The invention also makes use of the general algebraic xe2x80x98coloringxe2x80x99 scheme of quasi-crystalline points provided in the paper by R. V. Moody, Jiri Pater, Colorings of quasi-crystals, Can. J. Phys. 72 )(1994) 442-452. It is pointed out that the technical results in these papers become possible only after the versatile definition of quasi-crystals introduced in the paper by R. V. Moody, Jiri Patera, Quasi-crystals and icosians, J. Phys. A: Math. Gen., 26 (1993) 2829-2853.
The principal property of the quasi-crystals is the aperiodicity. An other important property is that given any finite quasi-crystal fragment it is impossible to deduce the position of that fragment in the quasi-crystal. The general properties of quasi-crystals, that are exploited according to the present invention, are the following:
a. Quasi-crystals exhibit aperiodicity in the strongest sense. A quasi-crystal contains no periodic subset. There are only a few distinct distances between adjacent points.
b. Quasi-crystals can be generated numerically or symbolically. Numerical implementations are very fast and simple but involve rounding, while symbolical implementations are exact, but may be slower and require more memory. Both types of generation may start with any point of the quasi-crystal. The algorithm involves only a small number of parameters. Distinct parameters lead to generation of distinct quasi-crystals. On a SUN(trademark) computer with 32-bit single processor running at 270 MHz, one can numerically generate well over 1,000,000 quasi-crystal points per second. All these implementation advantages and drawbacks are discussed hereinbelow.
c. The quasi-crystal is deterministic. Its points are completely determined by the parameters of the algorithm: no single point can be added or removed without creating a defect in the quasi-crystal.
d. A finite size fragment of a quasi-crystal does not allow one to identify the quasi-crystal, i.e. to find its other points.
e. There is an infinite number (i.e. cannot be enumerated by the integers) of distinct quasi-crystals in any dimension. Depending on the length of the fragment, the approximate length of the window can be established, but not its position in the quasi-crystal.
f. Quasi-crystal generation may start from any point x in the quasi-crystal.
A summary explanation of the properties of the method according to the invention that achieve the advantages given above are listed below:
A quasi-crystal is a uniformly discrete and relatively dense aperiodic set of points in any dimension. Binary strings are then associated to the points, this is called the coloring of the quasi-crystal. There exists infinitely many ways to color a quasi-crystal. Some coloring prescriptions, which are called admissible algebraic rules, have the property that points of the same color within a quasi-crystal form a subquasi-crystal. The color of a point is determined by its position in the quasi-crystal in any coloring. In the encryption methods, colored quasi-crystal points are used to mask the digital data of any length and of corresponding dimension according to a prescribed encrypting function. Not all colorings lead to cryptographically secure ciphers. In watermarks, colored quasi-crystal points are used to watermark any digitized document. Again, not all coloring leads to secure and robust watermarks.
There is a very fast mathematical algorithm for numerical generation and coloring of the quasi-crystal points starting from any of its points. In the encryption methods, the same algorithm may be used during encryption and decryption.
Since a quasi-crystal contains no periodic subsets and since it is infinite in all directions, repeated words are masked by different sets of points.
An encryption key contains the real numbers which specify: (i) particular quasi-crystals (encryption may involve multiple quasi-crystals as described below); and (ii) the coloring parameters assigning a color to the selected quasi-crystal points. In addition the key may contain other information, namely the encryption function, parameters specifying the subquasi-crystal which determines the position where random points are to be inserted, information for randomization of the encrypted form of the total of data, and others.
The coordinates of quasi-crystal points, hence also their colors, cannot be determined from a finite size fragment of the quasi-crystal without the encryption key. More precisely, any finite quasi-crystal fragment could belong to infinitely many complete quasi-crystals. Moreover, within each such quasi-crystal the fragment is always repeated non periodically and infinitely many times at various positions. In fact repetitions of the fragment within a given quasi-crystal form another quasi-crystal which parameters depend on the fragment.
Quasi-crystal generation and also encryption/decryption can either start from one or from several seed points simultaneously. This follows from the fact that it is possible to generate all quasi-crystals from any of its points, and from the fact that the positions of the points are completely determined by the parameters of the encryption key.
In numerical implementations, theoretical properties of quasi-crystals cannot all be exploited in a direct way, and this for two reasons: finite precision of their arithmetic operations and the practical limits on size of the integers which can be handled in large quantities by computers.
In the present invention, the two sides of the process (transmission, identification, etc.) have secretly selected, using the key, one or several particular quasi-crystals and colorings. In the identification process one side may ask the other to demonstrate its knowledge of some properties of the selected quasi-crystal (a few points in a given position relatively to the seed point, for example).
Another feature of the present invention which enlarges the practical scope of its applicability while imposing only a miniscule computing overhead, is the possible exploitation of coloring of quasi-crystal points during encryption and decryption by a finite number of colors. A color of a point is an integer which is associated to this point. One point may carry more than one color (multiple coloring). It may be advantageous to use algebraic colorings which guarantee that monochromatic subsets of quasi-crystal points are also quasi-crystals. Then one can use points of different colors for different tasks (for example simultaneous transmission of several messages).